﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>

//递归和非递归分别实现求第n个斐波那契数
//递归
//int fib(int n)
//{
//	if (n<=2)
//	{
//		return 1;
//	}
//	else
//	{
//		return fib(n - 1) + fib(n - 2);
//	}
//}
//
////非递归
//int fib_(int n)
//{
//	int a = 1;
//	int b = 1;
//	int c = 1;
//	while (n>2)
//	{
//		c = a + b;
//		a = b;
//		b = c;
//		n--;
//	}
//	return c;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int fib_n = fib(n);		//递归
//	printf("%d\n", fib_n);
//	int fib_n_ = fib(n);	//非递归
//	printf("%d\n", fib_n_);
//	return 0;
//}


//编写一个函数实现n的k次方，使用递归实现。
//double power(int n, int k) {
//    if (k==0)
//    {
//        return 1;
//    }
//    else if (k>0)
//    {
//        return n * power(n, k - 1);
//    }
//    else
//    {
//        return 1.0 / power(n, -k);
//    }
//}
//
//int main() {
//    int n = 0;
//    int k = 0;
//    scanf("%d %d", &n, &k);
//    double result = power(n, k);
//    printf("%lf\n", result);
//    return 0;
//}


//写一个递归函数DigitSum(n)，输入一个非负整数，返回组成它的数字之和
//例如，调用DigitSum(1729)，则应该返回1 + 7 + 2 + 9，它的和是19
//输入：1729，输出：19
//int DigitSum(int n)
//{
//	if (n>0)
//	{
//		return n % 10 + DigitSum(n / 10);
//	}
//	else
//	{
//		return 0;
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int sum = DigitSum(n);
//	printf("%d\n", sum);
//	return 0;
//}


//递归和非递归分别实现求n的阶乘（不考虑溢出的问题）
//int fac(int n)
//{
//	if (n>0)
//	{
//		return n * fac(n - 1);
//	}
//	else
//	{
//		return 1;
//	}
//}
//int no_fac(int n)
//{
//	int fac = 1;
//	while (n>0)
//	{
//		fac *= n;
//		n--;
//	}
//	return fac;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int n_fac1 = fac(n);		//递归
//	int n_fac2 = no_fac(n);		//非递归
//	printf("%d\n", n_fac1);
//	printf("%d\n", n_fac2);
//	return 0;
//}


//递归方式实现打印一个整数的每一位
//void Print(int n)
//{
//	if (n>9)
//	{
//		Print(n / 10);
//	}
//	printf("%d ", n % 10);
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	Print(n);
//	return 0;
//}


//在一个整型数组中，只有一个数字出现一次，其他数组都是成对出现的，请找出那个只出现一次的数字。
//
//例如：
//
//数组中有：1 2 3 4 5 1 2 3 4，只有5出现一次，其他数字都出现2次，找出5
// 法一
//int main()
//{
//	int arr[] = { 1, 2, 3, 4, 5, 1, 2, 3, 4 };
//	int sz = sizeof(arr) / sizeof(arr[0]);
//	for (int i = 0; i < sz; i++)
//	{
//		int flag = 1;
//		for (int j = 0; j < sz; j++)
//		{
//			if (arr[i]==arr[j] && i!=j)
//			{
//				flag = 0;
//				break;
//			}
//		}
//		if (flag)
//		{
//			printf("%d\n", arr[i]);
//		}
//	}
//	return 0;
//}

//法二
//int find_single_dog(int arr[], int sz)
//{
//    int ret = 0;
//    int i = 0;
//    for (i = 0; i < sz; i++)
//    {
//        ret ^= arr[i];
//    }
//    return ret;
//}
//int main()
//{
//    int arr[] = { 1,2,3,4,5,1,2,3,4 };
//    int sz = sizeof(arr) / sizeof(arr[0]);
//    int dog = find_single_dog(arr, sz);
//    printf("%d\n", dog);
//    return 0;
//}


//不允许创建临时变量，交换两个整数的内容
//int main()
//{
//	int a = -10;
//	int b = 20;
//	a = a ^ b;
//	b = a ^ b;
//	a = a ^ b;
//	printf("a=%d, b=%d\n", a, b);
//	return 0;
//}


//写一个函数返回参数二进制中 1 的个数。
//比如： 15    0000 1111    4 个 1
////法一
//int fun1(int n)
//{
//	int count = 0;
//	for (int i = 0; i < 32; i++)
//	{
//		if (n&1<<i)
//		{
//			count++;
//		}
//	}
//	return count;
//}
////法二
//int fun2(int n)
//{
//	int count = 0;
//	while (n)
//	{
//		count++;
//		n = n & (n - 1);
//	}
//	return count;
//}
////法三
//int fun3(int n)
//{
//	int count = 0;
//	while (n)
//	{
//		if (n % 2 == 1)
//			count++;
//		n = n / 2;
//	}
//	return count;
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	int count1 = fun1(n);
//	int count2 = fun2(n);
//	int count3 = fun3(n);
//	printf("%d\n", count1);
//	printf("%d\n", count2);
//	printf("%d\n", count3);
//	return 0;
//}


//获取一个整数二进制序列中所有的偶数位和奇数位，分别打印出二进制序列
//void fun(int n)
//{
//	//奇数位
//	for (int i = 1; i <= 32; i+=2)
//	{
//		if (n & 1 << (i-1))
//		{
//			printf("1 ");
//		}
//		else
//		{
//			printf("0 ");
//		}
//	}
//	printf("\n");
//	//偶数位
//	for (int i = 2; i <= 32; i += 2)
//	{
//		if (n & 1 << (i - 1))
//		{
//			printf("1 ");
//		}
//		else
//		{
//			printf("0 ");
//		}
//	}
//}
//int main()
//{
//	int n = 0;
//	scanf("%d", &n);
//	fun(n);
//	return 0;
//}


//编程实现：两个int（32位）整数m和n的二进制表达中，有多少个位(bit)不同？ 
//输入例子:
//1999 2299
//输出例子 : 7
// //法一
//int fun1(int m, int n)
//{
//	int count = 0;
//	for (int i = 0; i < 32; i++)
//	{
//		if ((m & 1 << i) != (n & 1 << i))
//		{
//			count++;
//		}
//	}
//	return count;
//}
////法二
//int fun2(int m, int n)
//{
//	int tmp = m ^ n;
//	int count = 0;
//	while (tmp)
//	{
//		tmp = tmp & (tmp - 1);
//		count++;
//	}
//	return count;
//}
//int main()
//{
//	int m = 0;
//	int n = 0;
//	scanf("%d %d", &m, &n);
//	int count1 = fun1(m, n);
//	int count2 = fun2(m, n);
//	printf("%d\n", count1);
//	printf("%d\n", count2);
//	return 0;
//}